#include<vector>
#include<iostream>

using namespace std;
void sort(vector<int> &vec,int tag,int idx)
{
    int inserted =vec[idx];

    int j;

    for(j=idx-tag;j>=0&&inserted<vec[j]; j-=tag)
    {
        vec[j+tag]=vec[j];
    }
    vec[j+tag]=inserted;
}

void base(vector<int> &vec)
{
    int len = vec.size();
    for(int i =len/2;i>0;i/=2)
        {
            for(int j= i;j<len;++j)
            {
                sort(vec,i,j);
            }
        }
}

int main()
{
    vector<int> dp={1,3,4,2,6,8,7};
    base(dp);
    for(const auto&i:dp)
    {
        cout<<i<<"\n";
    }
}



  
